package main

import (
	"fmt"
	"strconv"
	"strings"
	"time"
)

func main() {
	//var str = "BBC ABCDAB ABCDABCDABDE"
	//var pattern = "ABCDABD"

	var str = "c++/go/cangjie/编程语言 - 文本搜索性能大比拼，谁才是字符串比较的性能王者？请看2024年度性能测试野榜排名——c++/go/cangjie/编程语言"
	//var str = "c++/go/ 测试文本 c++/go/"
	var text = strings.Builder{} //  使用 strings.Builder 构建超多文本，string 变量超过10万行文本以后拼接会非常卡
	var num = 1000000            // 100万行文本

	for i := 0; i < num; i++ {
		//text += str + strconv.Itoa(i) + "\n" // 放弃使用 string 类型的变量拼接字符串，这种方式超过10万行非常慢
		// 文本后面 + 数字编号，保证每一行都是不同的
		if i%2 == 0 {
			//偶数行不追加换行符，保持前后有相同字符串，kmp算法匹配指定字符串时，就会跳过公共前缀，便于测试算法的性能，否则就跟普通的BF算法没有区别了
			text.WriteString(str)
		} else {
			text.WriteString("\n" + str + strconv.Itoa(i) + "\n")
		}

	}
	// 设置最后一行为固定字符串，方便我们查找
	var lastRowStr = str + strconv.Itoa(num+1)
	text.WriteString(lastRowStr)
	var pos = -1

	// 由于100万文本中含有中文，无法直接按照索引获取字符比较，因此我们将原始字符串转为 []rune
	textRune := []rune(text.String())
	lastRowStrRune := []rune(lastRowStr)
	// ↑↑↑  以上构建待处理的字符串过程放置在本次文本比较时间之间之外 ，我们本次只是测试文本比较性能 ↑↑↑

	startTime := time.Now()
	// 循环测试 10 次
	loopCount := 10
	for i := 0; i < loopCount; i++ {
		pos = findStr(textRune, lastRowStrRune)
	}
	useMs := time.Now().Sub(startTime).Milliseconds()
	fmt.Println("100万行文本字符串查找目标字符串(KMP算法)，字符串位置：", pos, " 单次耗时(ms): ", useMs/10)
}

// KMP 算法理解起来比较费劲，本篇需要数学理论支撑才能看懂代码
// 这里展示的代码基本是将阮一峰这篇文章中的计算过程翻译为程序代码，文章地址：https://kb.cnblogs.com/page/176818/

// @pattern 表示模式参数(待查找的字符串)
func getNext(patternRune []rune) []int {
	//patternRune := []rune(pattern)
	var length = len(patternRune)
	// next 数组默认全部填充 0
	var next = make([]int, length, length)

	var j = 0
	var leftStr = ""
	var rightStr = ""

	// 第一个元素的匹配值默认已经是0，这里只需要从第2个元素（索引从1开始）计算相关的 next 匹配表
	for i := 1; i < length; i++ {
		j = 0
		for j < i {
			// 优先匹配最长前缀和后缀
			leftStr = string(patternRune[0 : i-j])    // 左侧字符串，表示可能的前缀
			rightStr = string(patternRune[j+1 : i+1]) // 右侧字符串，表示可能的后缀
			if leftStr == rightStr {
				//fmt.Println("next - 索引：", i, ", left: ", leftStr, " rightIndex:", j+1, ",  right: ", rightStr, " next 部分匹配值：", string(patternRune[0:i-j]))
				next[i] = len(patternRune[0 : i-j])
				break
			}
			j++
		}
	}
	return next
}

// @origin 原始字符串
// @pattern 模式字符串(需要寻找的字符串)
func findStr(originRune []rune, patternRune []rune) int {
	// vector<int> next = getNext(pattern);
	var next = getNext(patternRune)

	//  搜索模式字符在目标字符中的位置
	//originRune := []rune(origin)
	//patternRune := []rune(pattern)
	var i = 0
	var j = 0
	var hasCommonStrNum = 0 // 公共字符个数

	for i < len(originRune) {
		//fmt.Println("匹配过程 - i=", i, "=", string(originRune[i]), " j=", j, "=", string(patternRune[j]))
		if originRune[i] == patternRune[j] {
			j++
		} else if j > 0 {
			hasCommonStrNum = next[j-1]
			j = 0
			// 这里和阮一峰文章计算偏移量有差异，文章是将模式字符串右移动，
			// 代码里面我们是将原始字符串左移，而模式字符串始终保持不动
			i = i - hasCommonStrNum
			continue
		} else {
			// j==0的情况就是第一个字符匹配失败了
			j = 0
		}
		i++

		if j == len(patternRune) {
			//fmt.Println("匹配成功,匹配区间：[ ", i-len(patternRune), " , ", i, " ) , 目标字符串："+pattern)
			return i - len(patternRune)
		}
	}

	return -1
}
